Parts · Full · Next ▶

top

The configuration linear program (configuration-LP) is a linear programming technique used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem.cite-ref-1[1]cite-ref-gilmore61-2-0[2] Later, it has been applied to the bin packingcite-ref-1-3-0[3]cite-ref-4[4] and job scheduling problems.cite-ref-0-5-0[5]cite-ref-6[6] In the configuration-LP, there is a variable for each possible configuration - each possible multiset of items that can fit in a single bin (these configurations are also known as patterns) . Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

Parts · Full · Next ▶